The embodiments herein relate generally to computer data storage systems and more particularly, to a process for buddy allocation without internal fragmentation.
Binary Buddy allocation is a widely used technique for allocating and deallocating memory in systems and devices that contain storage that requires dynamic allocation and deallocation. Binary Buddy allocation has a number of desirable properties. It performs a single allocation or deallocation in time proportional to ┌log 2N┐ where N is size of the largest block under management. It does this while requiring only ┌log 2 log 2N┐+1 bits of information to be associated with each block, where N is the size of the largest block under management by the allocator. It coalesces released blocks on the fly, which is to say that a deallocated block is coalesced with neighboring free blocks at the moment of deallocation, so that beyond the action of individual allocations and deallocations, no other processing is necessary in order to keep free blocks fully coalesced.
Binary Buddy allocation can provide for high alignment of allocations which means that it can effortlessly provide 2┌log 2R┐ alignment for a request of R storage units, i.e., alignment at least as great as the request size, subject to the alignment of the entire memory region it is working within.
Binary Buddy allocation has a serious shortcoming however. Because it is only able to allocate and deallocate blocks whose size is a power of two, the difference between the amount of storage requested and the nearest larger power of two is wasted. This form of waste is known as internal fragmentation as the unused storage is internal to the block the allocator returns for a request and is unavailable to service other requests.
Embodiments of the disclosed invention solve these problems.